from itertools import accumulate
from typing import List
from collections import deque
from math import inf
# 队列    61/97
# class Solution:
#     def shortestSubarray(self, nums: List[int], k: int) -> int:
#
#         result = 100
#         d = []
#         for index, num in enumerate(nums):
#             while d and d[0] < 0:
#                 d.pop(0)
#             d.append(num)
#             sum_ = sum(d)
#
#             if sum_ >= k:
#                 while d and sum_ >= k:
#                     result = len(d) if len(d) < result else result
#                     d.pop(0)
#                     sum_ = sum(d)
#
#                 while d and d[0] < 0:
#                     d.pop(0)
#                     sum_ = sum(d)
#                     if sum_ >= k:
#                         result = len(d) if len(d) < result else result
#
#         return result if result != 100 else -1


# 前缀和 + 单调队列    97/97
class Solution:
    def shortestSubarray(self, nums: List[int], k: int) -> int:
        # sums = [sum(nums[:i]) for i in range(1, len(nums) + 1)]   # 超时
        sums = list(accumulate(nums))
        result = inf
        q = deque([(0, -1)])  # nums = [1] k = 1
        for index, s in enumerate(sums):
            while q and q[-1][0] >= s:
                q.pop()
            while q and s - q[0][0] >= k:
                length = index - q[0][1]
                result = length if length < result else result
                q.popleft()  # 两端
            q.append((s, index))
        return result if result != inf else -1


# 对拍 双指针
class Solution2:
    def shortestSubarray(self, nums: List[int], k: int) -> int:
        result = inf
        for index1, num1 in enumerate(nums):
            sum_ = num1
            flag = False
            for index2 in range(index1, len(nums)):
                num2 = nums[index2]
                if index1 != index2:
                    sum_ += num2
                if sum_ >= k:
                    length = index2 - index1 + 1
                    result = length if length < result else result
                    flag = True
                    break
            if flag:
                continue
        return result if result != inf else -1


if __name__ == '__main__':
    # nums = [-28, 81, -20, 28, -29]
    # k = 89
    #
    # nums = [2, -1, 2]
    # k = 3
    #
    # nums = [1, 2]
    # k = 4
    #
    # nums = [1]
    # k = 1
    #
    # nums = [84, -37, 32, 40, 95]
    # k = 163
    #
    # nums = [84, -37, 32, 40, 95]
    # k = 167

    nums = [-34,37,51,3,-12,-50,51,100,-47,99,34,14,-13,89,31,-14,-44,23,-38,6]
    k = 151
    result = Solution().shortestSubarray(nums, k)
    print(result)
    result2 = Solution2().shortestSubarray(nums, k)
    print(result2)
